class ListaD
{
public:
    struct Iterator; // Declaratie forward
    static const Iterator END; // Iterator NULL
    // Constructor - Initializarea listei
    ListaD() { head = tail = nullptr; /*Se creeaza lista vida*/ }
    // Destructor - Distrugerea listei
    ~ListaD() { if(!isEmpty()) clear(); } 
    void push_front(int elem); // Inserare in fata primului nod
    void push_back(int elem);  // Inserare dupa ultimul nod
    void insert_before(int elem, Iterator nod); // Inserare inainte de nod
    void insert_after(int elem, Iterator nod);  // Inserare dupa nod
    Iterator search(int value) const; // Cauta value in lista
    void pop_front(); // Elimina nodul din fata
    void pop_back();  // Elimina ultimul nod
    void remove(Iterator nod); // Elimina nodul nod
    // Returneaza un iterator catre inceputul listei
    Iterator front() const { return Iterator(head); }
    // Returneaza un iterator catre nodul tail
    Iterator back() const { return Iterator(tail); }
    bool isEmpty() const { return head == nullptr; } // Este lista vida?
    void clear(); // Stergerea completa a listei
 
private:
    struct Nod  // Clasa Helper; Implementeaza un nod de lista
    {
        int data;   // informatia propriu-zisa
        Nod * next; // urm
        Nod * previous; // ant
    };
    Nod * head; // prim
    Nod * tail; // ultim
public:
    struct Iterator // Un pointer inteligent
    {
        friend class ListaD; // Lista are acces la membrii privati ai lui Iterator
        Iterator() { list = nullptr; }
        Iterator(Nod * ls) { list = ls; }
        // Supraincarc operatorul * (dereferentiere)
        int& operator*() { if(list != nullptr) return list->data; else throw "Null iterator!"; }
        // Prefix - Trec la urmatorul nod
        Iterator& operator++() { list = list->next; return *this; } 
        // Postfix
        Iterator operator++(int) { Iterator temp = *this; ++(*this); return temp; }
        // Prefix - Trec la nodul anterior
        Iterator& operator--() { list = list->previous; return *this; } 
        // Postfix
        Iterator operator--(int) { Iterator temp = *this; --(*this); return temp; }
        bool operator==(const Iterator& it) const { if(it.list == this->list) return true; else return false; }
        bool operator!=(const Iterator& it) const { if(!(it == *this)) return true; else return false; }
    private:
        Nod * list;
    };
};